package com.hanxiaozhang.no10leetcode.tree;

import org.apache.poi.ss.formula.functions.T;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈给一棵二叉树，其中仅包含0-9的数字，从根到叶节点可以代表为一个数字〉
 * 实例1：
 * .    1
 * .   / \
 * .  2   3
 * 输入：root = [1,2,3]
 * 输出：25
 * 解释：
 * 从根到叶子节点路径 1->2 代表数字 12
 * 从根到叶子节点路径 1->3 代表数字 13
 * 因此，数字总和 = 12 + 13 = 25
 * 示例 2：
 * .       4
 * .      / \
 * .     9   0
 * .   /  \
 * . 5     1
 * 输入：root = [4,9,0,5,1]
 * 输出：1026
 * 解释：
 * 从根到叶子节点路径 4->9->5 代表数字 495
 * 从根到叶子节点路径 4->9->1 代表数字 491
 * 从根到叶子节点路径 4->0 代表数字 40
 * 因此，数字总和 = 495 + 491 + 40 = 1026
 *
 * @author hanxinghua
 * @create 2024/4/25
 * @since 1.0.0
 */
public class No129SumRootToLeafNumbers {

    public static void main(String[] args) {


        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);

        TreeNode tree2 = new TreeNode(4);
        tree2.left = new TreeNode(9);
        tree2.right = new TreeNode(0);
        tree2.left.left = new TreeNode(5);
        tree2.left.right = new TreeNode(1);

        System.out.println(method1(tree1));
        System.out.println(method1(tree2));

    }


    /**
     * 方法1
     *
     * @param tree
     * @return
     */
    private static Integer method1(TreeNode tree) {

        Integer sum = 0;
        if (tree == null) {
            return sum;
        }

        List<List<String>> results = new ArrayList<>();
        List<String> result = new ArrayList<>();

        backTrack(results, result, tree);

        for (List<String> list : results) {
            sum += Integer.parseInt(String.join("", list));
        }

        return sum;
    }

    private static void backTrack(List<List<String>> results, List<String> result, TreeNode tree) {

        result.add(String.valueOf(tree.val));

        if (tree.left == null && tree.right == null) {
            results.add(new ArrayList<>(result));
            result.remove(result.size() - 1);
            return;
        }


        if (tree.left != null) {
            backTrack(results, result, tree.left);
        }

        if (tree.right != null) {
            backTrack(results, result, tree.right);
        }

        result.remove(result.size() - 1);

    }


}
